package B;

public class Main2 {
    public static void main(String[] args) {
        int[][] arr={{1, 2, -3},{ 3 ,4 ,-5},{ -5, -6, -7}};
        System.out.println(maxSum(arr));
    }
    public static int maxSum(int[][] matrix){
        int m=matrix.length;
        int n=matrix[0].length;
        int[][] res=new int[m+1][n];
        for(int i=1;i<m;i++){
            for(int j=0;j<n;j++){
                res[i][j]=res[i-1][j]+matrix[i-1][j];
            }
        }
        int max=res[0][0];
        int[] ans=new int[4];
        for(int top=0;top<m;top++){
            for(int bottom=top;bottom<m;bottom++){
                int[] temp=new int[n];
                for(int i=0;i<n;i++){
                    temp[i]=res[bottom][i]-res[top][i];
                }
                int sum=temp[0];
                int start=0;
                for(int p=1;p<n;p++){
                    if(sum<=0){
                        start=p;
                        sum=temp[p];
                    }else{
                        sum+=temp[p];
                    }
                    max=Math.max(max,sum);
                }
            }
        }
        return max;
    }

}
